//引用了图结构及图结构所需的字典结构
class ValuePair{ //存储原始值
    constructor(key,value) { //单个的字典值的节点
        this.key = key
        this.value = value
    }
    toString(){
        return `[${this.key}:${this.value}]` //单个值节点转成字符串
    }
}

class Dictionary{
    constructor(){
        this.table = {} //这个对象就是存储数据的内存空间，key就是内存地址，value就是里面的值
    }
    toStringFN(item){ //形参item就等同于key意思
        if(item === null){ //如果传入的key是null
            return ""
        }else if(item === undefined){ //如果传入的是undefined
            return "Undefined"
        }else if(typeof item === "string" || item instanceof String){ //如果传入的是与字符串有关的
            return `${item}`
        }
        //如果以上情况都不是
        return item.toString()
    }
    hasKey(key){ //判断是否已经在对象中存储了这个值
        return this.table[this.toStringFN(key)] !== undefined
        //因为我们访问的是 已经存在的对象 的key，访问对象的属性，如果返回的不是undefined，则表示存在，返回undefined则表示不存在
    }
    set(key,value){ //往字典里面存储值
        //先判断是否存在
        if(key != null && value != null){
            let tablekey = this.toStringFN(key) //得到一个key
            this.table[tablekey] = new ValuePair(key,value) //存储值
        }
        return false //如果为空返回false
    }
    remove(key){ //删除字典里的某个key所指向的值
        //删除一个值前提是得有这个值
        if(this.hasKey(key)){
            delete this.table[this.toStringFN(key)] //如果有这个值则删除
        }
        return false //没有则返回false
    }
    get(key){ //根据传入的key获取对应的值
        return this.table[this.toStringFN(key)]
    }
    keyValues(){ //获取所有名值对
        let ValuePairs = []
        for(let k in this.table){
            if(this.hasKey(key)){
                ValuePairs.push(this.table[k])
            }
        }
        return ValuePairs
    }
    keys(){ //获取所有名值对的key名
        return this.keyValues().map(item => item.key)
    }
    values(){ //获取所有名值对的value值
        return this.keyValues().map(item => item.value)
    }
    forEach(cb){ //遍历，接收一个回调函数
        let valuePairs = this.keyValues()
        for(let index = 0; index < valuePairs.length; index++){
            cb(index,valuePairs[index].value,valuePairs) //index item arr 这里我改了第二个valuePairs[index].value
        }
    }
    size(){ //获取长度
        return this.keyValues().length
    }
    clear(){ //清空
        this.table = {}
    }
    isEmpty(){ //是否为空
        return this.size() === 0 //如果长度为0则表示是空
    }
    toString(){
        if(this.isEmpty()){
            return ""
        }
        let valuePairs = this.keyValues()
        let objStr = ""
        for(let i = 0; i < valuePairs.length; i++){
            objStr = `${objStr},${valuePairs[i].toStringFN()}` //这里我改了最后的toStringFN
        }
        return objStr.slice(1) //去掉前面的逗号
    }
}

class Graph{ //图
    constructor(isDirected = false) {
        this.isDirected = isDirected //是否为有方向图
        this.vertices = [] //存储顶点的列表
        this.adjList = new Dictionary() //用一个字典结构来存储邻接表，即adjList是用来存储vertices的，vertices是用来存储点与点之间的关系的
    }

    //先添加点，再添加边，没有点哪来的边
    addVertex(v){ //添加点
        if(!this.vertices.includes(v)){ //如果列表中没有该点，才添加该点
            this.vertices.push(v) //顶点列表中添加该点
            this.adjList.set(v,[])
        }
    }

    addEdge(v,w){ //添加边，用两个点模拟形成一条边
        if(!this.adjList.get(v)){ //如果该点不存在则添加该点
            this.addVertex(v)
        }
        if(!this.adjList.get(w)){ //如果该点不存在则添加该点
            this.addVertex(w)
        }
        //此时这两个点没有关系，需要添加关系
        this.adjList.get(v).value.push(w) //将点w添加到点v的邻接表中
        if(!this.isDirected){ //如果是无方向图，则两个点都是互通的
            this.adjList.get(w).value.push(v) //将点v添加到点w的邻接表中
        }
    }

    getVertices(){ //获取所有顶点
        return this.vertices
    }

    getAdjList(){ //获取所有的边
        return this.adjList
    }

    toString(){
        let s = "\n" //在空字符串中价格换行，更好看更对称，其实s就是一个空袋子，先在内存中进行运算，最后再一起集中的，更节省性能
        for(let i = 0; i < this.vertices.length; i++){
            console.log("this.vertices[i]是："+this.vertices[i])
            s += `${this.vertices[i]} -> `
            let neighbors = this.adjList.get(this.vertices[i]).value
            console.log("neighbors是："+neighbors)
            for(let j = 0; j < neighbors.length; j++){
                console.log("neighbors[j]是："+neighbors[j])
                s += `${neighbors[j]},`
            }
            s = s.slice(0,s.length-1)
            s += `\n` //加个换行符更好看
        }
        return s
    }
}

//引用了队列结构
class Queue{
    constructor(){
        this.count = 0 //计数器
        this.items = {} //队列的数据仓库
    }
    enqueue(...eles){ //在队列尾部增加一项
        for(let i = 0, len = eles.length; i < len; i++){
            this.items[this.count] = eles[i] //采用计数器当前值（自然数）为下标key，存储实际数据
            this.count++ //每次push进一个数据，计数器自增1
        }
    }
    isEmpty(){
        return !this.count
    }
    dequeue(){ //移除队列当前最前面一项
        if(this.isEmpty()){
            return undefined
        }else{
            let result = this.items[0] //先将队列最前面的那一项保存下来，因为移除了最前面一项，队列后面剩下的所有项都会相应地往前挪一位
            for(let i = 0; i < this.count - 1; i++){
                this.items[i] = this.items[i + 1] //循环将剩下队列的每一项向前挪一位，就是将后一项值赋值给前一项
            }
            delete this.items[this.count - 1] //当剩下所有的项都往前挪了一位，最后一位会赋值给倒数第二位，这样就有两个是相同的，所以删除最后一位
            this.count-- //每次删除一位，相应的计数器要自减1
            return result //返回我们一开始保存好的队列要删除的第一位
        }
    }
    peek(){ //先进先出，返回队列里最早添加的也是会最先被删除的那一项
        if(this.isEmpty()){
            return undefined
        }else{
            return this.items[0]
        }
    }
    size(){
        return this.count
    }
    toString(){
        if(this.isEmpty()){
            return ""
        }else{
            let objString = ""
            for(let i = 0; i < this.count; i++){
                objString = `${objString},${this.items[i]}`
            }
            return objString.slice(1)
        }
    }
    [Symbol.iterator](){ //手动添加一个迭代器接口
        let self = this //先保存好当前的this
        let index = 0 //定义一个索引
        return {
            next(){
                if(index < self.count){ //如果没有遍历结束，则一个个返回当前值
                    return {
                        value:self.items[index++], //运用了闭包
                        done:false //false表示没有遍历完成
                    }
                }else{ //否则如果变量结束，则返回undefined
                    return {
                        value:undefined,
                        done:true //true表示遍历结束
                    }
                }
            }
        }
    }
}

//引用了栈结构
class Stack{
    constructor(){
        this.count = 0 //栈的计数器
        this.items = {} //栈的数据仓库
    }
    push(...eles){ //添加一个值
        for(let i = 0,len = eles.length; i < len; i++){
            this.items[this.count] = eles[i] //采用计数器当前值（自然数）为下标key，存储实际数据
            this.count++ //每次push进一个数据，计数器自增1
        }
    }
    size(){ //返回栈的长度
        return this.count //每次查询的时候直接返回当前的计数器的值
    }
    isEmpty(){ //判断栈是否为空
        return !this.count //判断是否为空，直接返回计数器的取反，0取反为true，大于零取反为false
    }
    pop(){ //删除栈顶值并返回被删除的值
        if(this.isEmpty()){ //先进行判断，如果栈内为空，直接返回undefined
            return undefined
        }

        //如果不走上面的if判断则表明栈非空，那么就走下面的代码
        this.count-- //先进行计数器自减1，减去1之后得到的就是未删除前栈顶值的下标key，如果不明白，用几个数代入就知道了
        let result = this.items[this.count] //得到栈顶的值
        delete this.items[this.count] //删除栈顶的值
        return result //并返回被删除的栈顶的值
    }
    peek(){ //先进后出，返回栈顶的值不对栈做任何修改
        if(this.isEmpty()){ //先进行判断，如果栈内为空，直接返回undefined
            return undefined
        }
        return this.items[this.count - 1] //否则返回当前的栈顶值
    }
    clear(){ //清空栈内数据
        while(!this.isEmpty()){ //当栈内为非空则一直进行这个循环，pop删除直到栈内没有数据为止
            this.pop()
        }
    }
    toString(){ //转字符串
        if(this.isEmpty()){ //先进行判断，如果栈内为空，直接返回空字符串""
            return ""
        }
        let resultString = "" //如果非空则先用一个变量保存，因为我们也不知道有多少个值，默认为空字符串
        for(let i = 0; i < this.count; i++){
            resultString = `${resultString},${this.items[i]}` //如果无法理解，代入几个数进去即可明白
        }
        return resultString.slice(1) //因为上面的模板字符串拼接方式会在第一位返回多一个逗号，所以要用slice方法删除逗号
    }
    forEach(cb){ //forEach方法接收一个回调函数
        for(let i = 0; i < this.count; i++){
            cb(i,this.items[i],this) //回调函数接收三个参数index，items，arr本身
        }
    }
    [Symbol.iterator](){ //手动添加一个迭代器接口
        let self = this //先保存好当前的this
        let index = 0 //定义一个索引
        return {
            next(){
                if(index < self.count){ //如果没有遍历结束，则一个个返回当前值
                    return {
                        value:self.items[index++], //运用了闭包
                        done:false //false表示没有遍历完成
                    }
                }else{ //否则如果变量结束，则返回undefined
                    return {
                        value:undefined,
                        done:true //true表示遍历结束
                    }
                }
            }
        }
    }
}

//生成图
let graph = new Graph()
graph.addEdge("A","B")
graph.addEdge("A","C")
graph.addEdge("A","D")
graph.addEdge("B","E")
graph.addEdge("B","F")
graph.addEdge("C","G")
graph.addEdge("C","D")
graph.addEdge("D","G")
graph.addEdge("D","H")
graph.addEdge("E","I")

console.log(graph.getVertices()) //获取图中所有顶点
console.log(graph.getAdjList()) //获取图中所有边

//定义三种状态
const Colors = { //定义三种状态
    WHITE:0, //表示该节点还没有被访问过
    GREY:1, //表示该节点被访问过，但该节点的相邻节点还没有被访问完
    BLACK:2 //表示该节点被访问过，并且该节点的相邻节点也都被访问完了
}

//把节点颜色初始化
function initializeColor(vertices){ //给传入的节点进行颜色初始化，默认是白色，表示没有被访问过
    const color = {} //类似一个映射表对象

    //因为getVertices()是得到一个节点的数组形式，所以用for循环进行遍历上色做标记
    for(let i = 0; i < vertices.length; i++){
        color[vertices[i]] = Colors.WHITE //默认是白色表示没有被访问过
    }
    return color //最后将这个映射表返回出去
}

//图结构的广度优先遍历，类似于数组的forEach
function breadthFirstSearch(graph,startVer,cb){ //图，开始遍历的节点，回调函数
    let vertices = graph.getVertices() //获取图中所有的节点并存储起来
    let adjList = graph.getAdjList() //存储邻接表，每一个节点与其他节点的关联表
    const color = initializeColor(vertices) //把存储起来的所有节点传入初始化函数，初始化所有节点的颜色
    const queue = new Queue() //新建队列，存储已经被遍历但相邻节点还没被访问的节点
    queue.enqueue(startVer) //添加已经遍历的节点，起始点
    while (!queue.isEmpty()){ //当队列里面不为空，表示已经有被遍历的节点的时候，我们需要对该节点的相邻节点做遍历
        let u = queue.dequeue() //把当前的起始点从队列中拿出来，下一次遍历就不会再遍历队列中的这个起始点了
        let neighbors = adjList.get(u).value //获取该起始节点的相邻节点，是一个数组形式，往get方法传一个key，可以得到对应的value

        //以上操作说明该起始节点被访问，但他的相邻节点还没有被遍历完，所以状态应该改为灰色
        color[u] = Colors.GREY

        //所以接下来用for循环来遍历它的相邻节点
        for(let i = 0; i < neighbors.length; i++){
            let w = neighbors[i] //开始遍历相邻节点
            if(color[w] === Colors.WHITE){ //该相邻节点必须是没有被访问过的，否则多个节点都是相连的就走了回头路了
                color[w] = Colors.GREY //u节点的这个相邻节点w访问到了，但是没有把这个相邻节点w的相邻节点都访问完，所以标记w节点为灰色

                //然后把w节点放到queue队列中，下一次就遍历w节点的相邻节点
                queue.enqueue(w) //w节点被添加到任务队列，while循环是只要任务队列中还有节点就会一直遍历下去
            }
        }

        //u节点被访问并且循环遍历完u节点的所有相邻节点，u节点就可以变为黑色状态了
        color[u] = Colors.BLACK

        //如果还有回调函数，那就把当前被遍历完成的节点传入回调函数执行
        if(cb){
            cb(u) //这一次值遍历完成了u节点，就执行u的回调函数
        }
    }
}

//试验一下成果，传入图与起始点与回调函数
breadthFirstSearch(graph,graph.getVertices()[0],function (vertices){
    console.log(`现在${vertices}被遍历了`)
})

//再搞一个搜索方法，搜索的写法和遍历很像
function BFS(graph,startVer){ //搜索方法
    let vertices = graph.getVertices() //获取图中所有的节点
    let adjList = graph.getAdjList() //存储邻接表，每一个节点与其他节点的关联表
    const color = initializeColor(vertices) //初始化所有节点的颜色
    const queue = new Queue() //新建队列，存储已经被遍历但相邻节点还没被访问的节点

    //distances和predecessors可以用于记录走到每个节点的最短路径
    const distances = {} //记录节点间的间距，即从初始节点走到每个节点需要多少步
    const predecessors = {} //记录一个节点的上一个节点是谁，映射关系，谁能走到你
    queue.enqueue(startVer) //添加已经遍历的节点，起始点
    for(let i = 0; i < vertices.length; i++){ //初始化所有节点
        distances[vertices[i]] = 0 //默认走到每个节点一开始都是0步
        predecessors[vertices[i]] = null //每个节点的上一个节点，默认为null
    }
    while (!queue.isEmpty()){ //当队列里面不为空，表示已经有被遍历的节点的时候，我们需要对该节点的相邻节点做遍历
        let u = queue.dequeue() //把当前的起始点从队列中拿出来，下一次遍历就不会再遍历队列中的这个起始点了
        let neighbors = adjList.get(u).value //获取该起始节点的相邻节点，是一个数组形式

        //以上操作说明该起始节点被访问，但他的相邻节点还没有被遍历完，所以状态应该改为灰色
        color[u] = Colors.GREY

        //所以用for循环来遍历它的相邻节点
        for(let i = 0; i < neighbors.length; i++){
            let w = neighbors[i] //开始遍历相邻节点
            if(color[w] === Colors.WHITE){ //该相邻节点必须是没有被访问过的，否则多个节点都是相连的就走了回头路了
                color[w] = Colors.GREY //u节点的这个相邻节点w访问到了，但是没有把这个相邻节点w的相邻节点都访问完，所以标记w节点为灰色
                distances[w] = distances[u] + 1 //w节点和u节点相距1
                predecessors[w] = u //w的上一个节点是u

                //然后把w节点放到queue队列中
                queue.enqueue(w)
            }
        }

        //循环完u节点的所有相邻节点，u节点就可以变为黑色状态了
        color[u] = Colors.BLACK
    }
    return {
        distances,
        predecessors
    }
}

console.log(BFS(graph,graph.getVertices()[0]))

//下面的代码是记录到每个节点所走过的每条路径
let data = BFS(graph,graph.getVertices()[0])

let start = graph.getVertices()[0] //起始点

for(let i = 1; i < graph.getVertices().length; i++){
    let end = graph.getVertices()[i] //目的地
    const path = new Stack() //新建一个栈结构表示路径，走哪儿

    //倒着走，从最后开始走，只要没走到起始节点就表示没有走完
    for(let v = end; v !== start; v = data.predecessors[v]){
        path.push(v) //往栈内添加走过的节点
    }
    path.push(start) //因为是倒着走，所以最后添加的肯定是起始节点
    let str = path.pop()
    while(!path.isEmpty()){
        str += "->" + path.pop()
    }
    console.log(str)
}